package leetcode;


/**
 * Created by Ghost on 2014/10/10 0010.
// */




public class Path_Sum {
    public boolean add(TreeNode root, int curSum, int sum){

        if(root==null){
            return false;
        }
        else if(curSum+root.val==sum && root.left ==null && root.right==null){
            return true;
        }

        boolean left = add(root.left, curSum+root.val, sum);
        //boolean right = add(root.right, curSum+root.val, sum);
        return left || add(root.right, curSum+root.val, sum);
    }
    public boolean hasPathSum(TreeNode root, int sum) {
        return add(root, 0, sum);
    }

    public static void main(String[] args){
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);

        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);

        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);

        root.right.right.right = new TreeNode(1);

        System.out.println(new Path_Sum().hasPathSum(root,22));
    }
}

































//
//class Parent{
//    private String inintParent = "initParet";
//    static String name = "Parent_hello";
//    {
//        System.out.println("parent non static block");
//        System.out.println(inintParent);
//    }
//    static{
//        System.out.println("parent static block");
//        System.out.println(name);
//    }
//    public Parent(){
//        System.out.println("parent constructor4");
//    }
//    public static void output(){
//        System.out.println(name);
//    }
//}
//
//class Child extends Parent{
//    static String name = "child_hello";
//    static String inintChild = "inintChile";
//    {
//        System.out.println("Child non static block");
//        System.out.println(inintChild);
//    }
//    static{
//        System.out.println("Child static block");
//        System.out.println(name);
//    }
//    public Child(){
//        System.out.println("child constructor");
//    }
//    public static void output(){
//        System.out.println(name);
//    }
//}
//public class Test{
//    public static void main(String[] args){
//        Parent parent = new Child();
//        parent.output();
//    }
//}









//interface A{
//    int x = 0;
//    void play();
//}
//interface B{
//    int y = 1;
//    void play();
//}
//interface C extends A,B{
//    D d = new D("PingPang");
//}
//class D implements C{
//    private String name;
//    public String getName(){
//        return name;
//    }
//    public D(String name){
//        this.name = name;
//    }
//    public void play(){
//        D d = new D("Football");
//        System.out.println(getName());
//        System.out.println(y);
//    }
//}
//public class TestInterface{
//    public static void main(String[] args){
//        D d = new D("hello");
//        d.play();
//    }
//}
